//给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的
//根节点的引用。 
//
// 一般来说，删除节点可分为两个步骤： 
//
// 
// 首先找到需要删除的节点； 
// 如果找到了，删除它。 
// 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：root = [5,3,6,2,4,null,7], key = 3
//输出：[5,4,6,2,null,null,7]
//解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
//一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
//另一个正确答案是 [5,2,6,null,4,null,7]。
//
//
// 
//
// 示例 2: 
//
// 
//输入: root = [5,3,6,2,4,null,7], key = 0
//输出: [5,3,6,2,4,null,7]
//解释: 二叉树不包含值为 0 的节点
// 
//
// 示例 3: 
//
// 
//输入: root = [], key = 0
//输出: [] 
//
// 
//
// 提示: 
//
// 
// 节点数的范围 [0, 10⁴]. 
// -10⁵ <= Node.val <= 10⁵ 
// 节点值唯一 
// root 是合法的二叉搜索树 
// -10⁵ <= key <= 10⁵ 
// 
//
// 
//
// 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。 
//
// Related Topics 树 二叉搜索树 二叉树 👍 1207 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-08-18 00:53:24
 * @description 450.删除二叉搜索树中的节点
 */
public class DeleteNodeInABst{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new DeleteNodeInABst().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode() {}
	TreeNode(int val) { this.val = val; }
	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

class Solution {
		 //找到，然后删除
    public TreeNode deleteNode(TreeNode root, int key) {
		TreeNode p=root,dummy=new TreeNode(Integer.MAX_VALUE),pre;
		dummy.left=root;
		pre=dummy;
		while (p!=null){
			if(p.val==key){
				adjust(p,pre);
				return dummy.left;
			}
			pre=p;
			p=key>p.val?p.right:p.left;
		}
		return dummy.left;
    }
	private void adjust(TreeNode root,TreeNode pre){
		//先判断当前节点有没有孩子节点
		//叶子节点，直接删除
		if(root.left==null&&root.right==null){
			if(root==pre.left) pre.left=null;
			else pre.right=null;
			//只有一个孩子节点，直接接到pre上
		}else if(root.left!=null^root.right!=null){
			TreeNode child=root.left!=null?root.left:root.right;
			if(root==pre.left){
				pre.left=child;
			}
			else pre.right=child;
			//两个都不为空，找到root的前驱或者后继p
			//把值赋给root，然后删除p
		}else {
			//前驱p,p的父节点p1
			TreeNode p=root.left,p1=null;
			while (p.right!=null){
				p1=p;
				p=p.right;
			}
			//当前节点赋值为前驱的值
			root.val=p.val;
			//如果前驱节点有父节点
			if(p1!=null){
				p1.right=p.left;
				//否则说明前驱就是当前节点的左子树根节点
			}else {
				root.left=p.left;
			}
		}
	}

	public TreeNode deleteNode1(TreeNode root, int key) {
		if(root==null) return root;
		if(root.val==key){
			if(root.right==null) return root.left;
			else {
				TreeNode tmp=root.right;
				while(tmp.left!=null) tmp=tmp.left;
				tmp.left=root.left;
				return root.right;
			}
		}
		if(root.val<key) root.right=deleteNode1(root.right,key);
		else root.left=deleteNode1(root.left,key);
		return root;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
